package test.day09;

/**
 * 排序链表
 */
public class SortList {
	public class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) { this.val = val; this.next = next; }
	}
	public ListNode sortList(ListNode head) {
		if(head == null || head.next == null) {
			return head;
		}
		ListNode slow = head, fast = head.next;
		while (fast != null && fast.next != null) {
			//慢指针一次一步，快指针一次两步，遍历完成之后慢指针指向中间
			slow = slow.next;
			fast = fast.next.next;
		}
		ListNode right = sortList(slow.next);
		//递归处理后半段
		slow.next = null;
		//切断前半段到后半段的联系
		ListNode left = sortList(head);
		//递归处理前半段
		return merge(left, right);
	}

	private ListNode merge(ListNode left, ListNode right) {
		ListNode dummy = new ListNode();
		ListNode curr = dummy;
		while (left != null && right != null) {
			if(left.val < right.val){
				curr.next = left;
				left = left.next;
			}else {
				curr.next = right;
				right = right.next;
			}
			curr = curr.next;
		}
		curr.next = left == null ? right : left;
		return dummy.next;
	}
}
